/**
 * 对二叉树的简单测试。
 * 
 */

#include <stdio.h>
#include <stdlib.h>

#include <cds/bintree.h>
#include "bintree_test_tools.h"
#include "test_tools.h"

static void bintree_basic_test(void)
{
    int test_nums[] = {
        487, 373, 498, 73, 310, 218, 151, 427, 109, 131, 162, 41, 494, 349, 246, 261, 
        124, 271, 367, 346, 358, 78, 114, 238, 103, 465, 77, 442, 470, 415, 304, 47, 
        217, 146, 52, 326, 140, 127, 356, 255, 216, 365, 5, 148, 7, 391, 280, 296, 
        321, 249, 159, 332, 210, 177, 40, 27, 118, 200, 107, 71, 58, 100, 195, 239, 
        496, 135, 93, 88, 37, 181, 254, 433, 95, 402, 51, 495, 198, 418, 458, 492, 
        323, 112, 207, 123, 430, 397, 139, 383, 499, 269, 104, 89, 337, 192, 406, 128, 
        267, 306, 407, 265, 315, 259, 257, 170, 82, 245, 437, 416, 447, 446, 115, 14, 
        504, 316, 486, 475, 57, 48, 178, 439, 436, 3, 136, 183, 270, 376, 472, 307, 
        147, 282, 43, 425, 491, 90, 116, 264, 250, 353, 500, 394, 175, 482, 154, 287, 
        318, 237, 196, 66, 400, 324, 330, 384, 45, 262, 171, 110, 67, 168, 419, 226, 
        453, 412, 248, 1, 79, 179, 158, 393, 19, 344, 225, 241, 202, 240, 194, 176, 
        190, 102, 399, 456, 11, 341, 411, 371, 44, 336, 133, 54, 372, 342, 281, 91, 
        279, 83, 357, 347, 405, 230, 39, 23, 388, 169, 343, 22, 205, 18, 50, 59, 
        182, 235, 335, 480, 284, 464, 334, 30, 273, 403, 288, 443, 355, 64, 130, 143, 
        477, 413, 423, 440, 505, 199, 460, 485, 422, 468, 144, 0, 150, 62, 268, 243, 
        408, 187, 309, 351, 55, 36, 375, 212, 32, 108, 166, 96, 305, 211, 184, 15, 
        493, 450, 377, 466, 484, 60, 6, 333, 111, 325, 173, 87, 165, 380, 509, 160, 
        289, 191, 322, 503, 186, 473, 295, 74, 379, 152, 424, 26, 258, 25, 328, 382, 
        219, 502, 511, 149, 260, 327, 278, 92, 448, 478, 63, 389, 506, 4, 285, 206, 
        8, 469, 97, 489, 209, 33, 242, 508, 350, 99, 300, 94, 435, 34, 20, 445, 
        13, 291, 362, 283, 156, 134, 2, 331, 421, 463, 348, 203, 98, 381, 231, 308, 
        174, 204, 317, 299, 396, 247, 387, 137, 234, 53, 28, 361, 228, 180, 121, 189, 
        302, 428, 501, 474, 320, 76, 368, 451, 398, 185, 197, 444, 223, 125, 481, 233, 
        488, 120, 461, 420, 386, 17, 314, 70, 142, 429, 244, 301, 274, 65, 276, 449, 
        312, 220, 303, 201, 378, 49, 370, 455, 272, 42, 510, 29, 352, 286, 297, 164, 
        208, 72, 275, 459, 479, 215, 311, 31, 126, 81, 10, 188, 263, 364, 21, 354, 
        229, 232, 457, 141, 462, 9, 153, 80, 119, 56, 369, 476, 213, 172, 222, 497, 
        417, 224, 84, 266, 68, 157, 360, 434, 294, 227, 483, 431, 163, 161, 507, 69, 
        85, 329, 392, 292, 319, 167, 390, 35, 101, 38, 414, 155, 438, 113, 395, 253, 
        122, 401, 441, 290, 454, 338, 339, 490, 298, 404, 313, 471, 363, 105, 24, 214, 
        193, 340, 221, 467, 256, 251, 409, 410, 117, 145, 75, 432, 252, 345, 366, 452, 
        132, 236, 61, 46, 129, 426, 277, 86, 16, 106, 293, 359, 138, 374, 12, 385,
    };
    int cnt = 0;
    int current = 0;
    size_t test_nums_len = sizeof(test_nums) / sizeof(int);
    struct rb_root *root = CREATE_RB_TREE();
    struct my_rb_node *pos = NULL;
    struct my_rb_node *n = NULL;
    
    /// 将所有元素插入二叉树。
    for (cnt = 0; cnt < test_nums_len; cnt++) {
        struct my_rb_node *new_node = CREATE_RB_NODE(test_nums[cnt]);
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
            break;
        }
        if (rb_insert_node(root, &new_node->rb_entry) != &new_node->rb_entry) {
            LOG_TEST_FAIL("failed to insert new node! ");
            printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
            break;
        }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes are all created!\n");
    }

    /// 测试顺序遍历
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt++;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    /// 测试逆序遍历
    cnt = test_nums_len - 1;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt--;
    }
    if (cnt == -1) {
        LOG_TEST_PASS("for each rb_node(inv) test succeed!\n");
    }

    /// 查找测试
    for (cnt = 0; cnt < test_nums_len; cnt++) {
        struct rb_node *new_node = rb_find_key(root, (unsigned long)&cnt);
        current = *(int*)(rb_get_node_key(root, new_node));
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d\n", cnt);
            break;
        }
        if (current != cnt) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes search testb succeed!\n");
    }

    // /// 删除树中所有的奇数，并测试
    for (cnt = 1; cnt < test_nums_len; cnt += 2) {
        struct rb_node *delete_node = rb_delete_key(root, (unsigned long)&cnt);
        if (delete_node == NULL) {
            LOG_TEST_FAIL("failed to delete node: ");
            printf("cnt: %d\n", cnt);
            break;
        }
        current = *(int*)(rb_get_node_key(root, delete_node));
        if (current != cnt) {
            LOG_TEST_FAIL("delete the wrong node: ");
            printf("cnt: %d， num: %d\n", cnt, current);
            break;
        }
        DESTROY_RB_NODE_BY_ENTRY(delete_node);
    }
    if (cnt == test_nums_len + 1) {
        LOG_TEST_PASS("all deleted!\n");
    }

    // cnt = 0;
    // rb_foreach_entry_safe(root, pos, n, rb_entry) {
    //     current = pos->key;
    //     printf("%d, ", current);
    //     cnt += 2;
    // }
    // printf("\n");
    // cnt = test_nums_len - 2;
    // rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
    //     current = pos->key;
    //     printf("%d, ", current);
    //     cnt -= 2;
    // }
    // printf("\n");

    /// 测试顺序遍历
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt += 2;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    /// 测试逆序遍历
    cnt = test_nums_len - 2;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != cnt) {
            LOG_TEST_FAIL("current: %d, cnt: %d\n", current, cnt);
            break;
        }
        cnt -= 2;
    }
    if (cnt == -2) {
        LOG_TEST_PASS("for each rb_node(inv) test succeed!\n");
    }

    /// 查找测试
    for (cnt = 0; cnt < test_nums_len; cnt += 2) {
        struct rb_node *new_node = rb_find_key(root, (unsigned long)&cnt);
        current = *(int*)(rb_get_node_key(root, new_node));
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d\n", cnt);
            break;
        }
        if (current != cnt) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes search test succeed!\n");
    }

    /// 针对已经被删除元素的查找测试
    for (cnt = 1; cnt < (test_nums_len * 4); cnt += 2) {
        struct rb_node *new_node = rb_find_key(root, (unsigned long)&cnt);
        if (new_node != NULL) {
            current = *(int*)(rb_get_node_key(root, new_node));
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == (test_nums_len * 4) + 1) {
        LOG_TEST_PASS("rb nodes search test succeed!\n");
    }

    /// 针对已经被删除元素的重复删除测试
    for (cnt = 1; cnt < (test_nums_len * 4); cnt += 2) {
        struct rb_node *new_node = rb_delete_key(root, (unsigned long)&cnt);
        if (new_node != NULL) {
            current = *(int*)(rb_get_node_key(root, new_node));
            LOG_TEST_FAIL("delete a node that is not existed! ");
            printf("cnt: %d, current: %d\n", cnt, current);
            break;
        }
    }
    
    if (cnt == (test_nums_len * 4) + 1) {
        LOG_TEST_PASS("rb nodes delete(no exist) test succeed!\n");
    }

    /// 针对已经被存在元素的重复插入测试
    struct my_rb_node *new_node = CREATE_RB_NODE(0);
    for (cnt = 0; cnt < (test_nums_len * 4); cnt += 2) {
        if (&new_node->rb_entry == rb_insert_node(root, &new_node->rb_entry)) {
            LOG_TEST_FAIL("insert a node that is already existed! ");
            printf("cnt: %d\n", cnt);
            break;
        }
    }
    DESTROY_RB_NODE(new_node);
    
    if (cnt == (test_nums_len * 4) + 2) {
        LOG_TEST_PASS("rb nodes insert(already exist) test succeed!\n");
    }

    DESTROY_RB_TREE(root);
}

static void bintree_simple_rotate_test(void)
{
    int test_nums[] = {
        2726, 2477, 171, 2286, 326, 1639, 175, 1619, 1034, 2951, 1322, 3184, 2638, 4046, 1032, 544, 
        610, 103, 770, 2338, 1988, 3711, 695, 2099, 534, 2710, 3202, 1427, 2906, 1111, 2781, 269, 
        1721, 1329, 248, 2993, 431, 962, 3027, 2283, 1004, 2213, 2681, 335, 1511, 1553, 1149, 1047, 
        2087, 3051, 2331, 3777, 2122, 243, 1201, 1936, 1168, 568, 1630, 2510, 2766, 3495, 3206, 110, 
        935, 2363, 1661, 2872, 767, 2359, 3407, 2673, 863, 3966, 3123, 782, 1842, 443, 1404, 1800, 
        1839, 1633, 229, 2596, 2428, 1042, 1829, 2287, 2704, 802, 2986, 3922, 3290, 2593, 82, 3393, 
        3159, 3623, 4035, 351, 434, 3765, 2902, 505, 3597, 1866, 2451, 1733, 3107, 3063, 3942, 353, 
        2716, 1187, 1081, 218, 2750, 804, 3476, 1066, 2402, 1471, 1778, 141, 2400, 1532, 394, 1594, 
        3751, 240, 451, 3600, 2589, 355, 698, 1969, 1513, 2991, 2467, 1366, 1246, 1564, 1245, 3082, 
        1251, 1932, 784, 3835, 3811, 4080, 1188, 1546, 2345, 2900, 3808, 414, 2053, 1989, 3405, 2187, 
        4010, 212, 2434, 3559, 2941, 3959, 251, 113, 3110, 2003, 836, 1948, 2739, 1453, 187, 1308, 
        3897, 750, 3194, 1749, 1591, 1014, 238, 1890, 3308, 281, 384, 2415, 2008, 3255, 987, 1540, 
        1504, 455, 2676, 430, 3203, 493, 3671, 3726, 299, 2930, 2586, 398, 919, 3934, 1193, 615, 
        3611, 283, 817, 572, 3599, 3987, 2184, 3758, 957, 1601, 3984, 79, 3118, 1104, 3233, 332, 
        648, 89, 1724, 3215, 3464, 1173, 3146, 302, 3116, 2852, 1703, 3020, 1671, 1186, 1994, 1618, 
        3774, 1953, 65, 3696, 2372, 3335, 555, 3912, 387, 2875, 565, 2898, 3783, 721, 1, 3537, 
        671, 3041, 1926, 1263, 1433, 866, 2836, 2789, 1300, 2979, 626, 2827, 1910, 636, 1575, 1236, 
        1857, 2828, 2196, 3357, 2259, 2577, 8, 938, 55, 2474, 587, 180, 1101, 720, 3022, 1729, 
        1889, 3563, 296, 2584, 2602, 680, 2232, 111, 3488, 786, 841, 3201, 2714, 1443, 2655, 3757, 
        2853, 550, 1325, 1351, 427, 388, 3132, 3244, 960, 4030, 3314, 1906, 4050, 3681, 2629, 1132, 
        1992, 2806, 3442, 380, 2217, 2120, 3594, 3133, 2069, 266, 3024, 703, 468, 2929, 354, 3815, 
        226, 2660, 1537, 2685, 165, 1791, 958, 1788, 2424, 3873, 2982, 2967, 3381, 469, 3154, 2212, 
        2429, 1298, 1408, 1566, 1853, 3979, 1643, 2369, 39, 1695, 1781, 2198, 1327, 2588, 3660, 3471, 
        3356, 488, 3451, 2808, 679, 2378, 1230, 3394, 3007, 2595, 3278, 1662, 81, 1324, 2874, 1252, 
        4095, 2590, 246, 2154, 2047, 888, 3152, 131, 241, 3108, 3780, 1178, 2225, 3297, 3920, 1535, 
        2029, 1838, 2703, 377, 342, 1121, 1096, 2658, 1286, 346, 942, 3441, 3214, 2846, 2377, 3573, 
        1747, 1265, 4012, 3544, 3506, 2012, 2123, 1051, 1582, 2179, 2016, 2604, 1652, 3695, 2498, 654, 
        3576, 3941, 4073, 2040, 904, 2522, 2513, 3854, 1114, 1773, 1301, 2427, 316, 106, 2686, 1757, 
        674, 1939, 2767, 2612, 4018, 3077, 2692, 3172, 2060, 2556, 1509, 1382, 546, 3553, 3316, 778, 
        3174, 1950, 2856, 1119, 3856, 3664, 1179, 1548, 3824, 2203, 2315, 1182, 1120, 3457, 3102, 1521, 
        1220, 108, 4059, 2769, 1849, 125, 1761, 22, 3505, 1452, 1986, 787, 3551, 3806, 1636, 2036, 
        701, 2810, 1087, 3489, 984, 2833, 1955, 2237, 3760, 2479, 2496, 3171, 1755, 2516, 3366, 632, 
    };
    int cnt = 0;
    int current = 0;
    size_t test_nums_len = sizeof(test_nums) / sizeof(int);
    struct rb_root *root = CREATE_RB_TREE();
    struct my_rb_node *pos = NULL;
    struct my_rb_node *n = NULL;
    int rotate_right_nums[] = {
        2726, 2477, 171, 2286, 326, 1639, 175, 1619, 1034, 2951, 1322, 3184, 2638, 4046, 1032, 544, 
        1839, 1633, 229, 2596, 2428, 1042, 1829, 2287, 2704, 802, 2986, 3922, 3290, 2593, 82, 3393, 
        3159, 3623, 4035, 351, 434, 3765, 2902, 505, 3597, 1866, 2451, 1733, 3107, 3063, 3942, 353, 
        2716, 1187, 1081, 218, 2750, 804, 3476, 1066, 2402, 1471, 1778, 141, 2400, 1532, 394, 1594, 
        3751, 240, 451, 3600, 2589, 355, 698, 1969, 1513, 2991, 2467, 1366, 1246, 1564, 1245, 3082, 
        1251, 1932, 784, 3835, 3811, 4080, 1188, 1546, 2345, 2900, 3808, 414, 2053, 1989, 3405, 2187, 
        4010, 212, 2434, 3559, 2941, 3959, 251, 113, 3110, 2003, 836, 1948, 2739, 1453, 187, 1308, 
    };
    size_t rotate_right_nums_len = sizeof(rotate_right_nums) / sizeof(int);
    int rotate_left_nums[] = {
        2429, 1298, 1408, 1566, 1853, 3979, 1643, 2369, 39, 1695, 1781, 2198, 1327, 2588, 3660, 3471, 
        3356, 488, 3451, 2808, 679, 2378, 1230, 3394, 3007, 2595, 3278, 1662, 81, 1324, 2874, 1252, 
        4095, 2590, 246, 2154, 2047, 888, 3152, 131, 241, 3108, 3780, 1178, 2225, 3297, 3920, 1535, 
        2029, 1838, 2703, 377, 342, 1121, 1096, 2658, 1286, 346, 942, 3441, 3214, 2846, 2377, 3573, 
        1747, 1265, 4012, 3544, 3506, 2012, 2123, 1051, 1582, 2179, 2016, 2604, 1652, 3695, 2498, 654, 
        3576, 3941, 4073, 2040, 904, 2522, 2513, 3854, 1114, 1773, 1301, 2427, 316, 106, 2686, 1757, 
    };
    size_t rotate_left_nums_len = sizeof(rotate_left_nums) / sizeof(int);
    int *test_nums_sorted = malloc(test_nums_len * sizeof(int));
    
    /// 将所有元素插入二叉树。
    for (cnt = 0; cnt < test_nums_len; cnt++) {
        struct my_rb_node *new_node = CREATE_RB_NODE(test_nums[cnt]);
        if (new_node == NULL) {
            LOG_TEST_FAIL("failed to create new node! ");
            printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
            break;
        }
        if (rb_insert_node(root, &new_node->rb_entry) != &new_node->rb_entry) {
            LOG_TEST_FAIL("failed to insert new node! ");
            printf("cnt: %d, num: %d\n", cnt, test_nums[cnt]);
            break;
        }
    }
    
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("rb nodes are all created!\n");
    }

    /// 顺序遍历，并将所有元素插入另一个数组。
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        test_nums_sorted[cnt] = current;
        cnt++;
    }

    if (cnt != test_nums_len) {
        printf("there may be some ndoes are not interted!\n");
    }

    // for (int i = 0; i < test_nums_len; i++) {
    //     printf("%d, ", test_nums_sorted[i]);
    // }
    // printf("\n");

    /// 进行第一次左旋操作
    for (cnt = 0; cnt < rotate_left_nums_len; cnt++) {
        struct rb_node *tmp_node = rb_find_key(root, (unsigned long)(rotate_left_nums + cnt));
        if (tmp_node == NULL) {
            LOG_TEST_FAIL("failed to find node! ");
            printf("cnt: %d, key: %d\n", cnt, rotate_left_nums[cnt]);
            break;
        }
        current = *(int*)(rb_get_node_key(root, tmp_node));
        if (rotate_left_nums[cnt] != current) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, key: %d, current: %d\n", 
                cnt, rotate_left_nums[cnt], current);
            break;
        }
        __rb_rotate_left(root, tmp_node);
    }

    if (cnt == rotate_left_nums_len) {
        LOG_TEST_PASS("rotation complete!\n");
    }

    /// 顺序遍历检查
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt += 1;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    cnt = test_nums_len - 1;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt -= 1;
    }
    if (cnt == -1) {
        LOG_TEST_PASS("for each rb_node test(inv) succeed!\n");
    }

    /// 进行第一次右旋操作
    for (cnt = 0; cnt < rotate_right_nums_len; cnt++) {
        struct rb_node *tmp_node = rb_find_key(root, (unsigned long)(rotate_right_nums + cnt));
        if (tmp_node == NULL) {
            LOG_TEST_FAIL("failed to find node! ");
            printf("cnt: %d, key: %d\n", cnt, rotate_right_nums[cnt]);
            break;
        }
        current = *(int*)(rb_get_node_key(root, tmp_node));
        if (rotate_right_nums[cnt] != current) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, key: %d, current: %d\n", 
                cnt, rotate_right_nums[cnt], current);
            break;
        }
        __rb_rotate_right(root, tmp_node);
    }

    if (cnt == rotate_right_nums_len) {
        LOG_TEST_PASS("rotation complete!\n");
    }

    /// 顺序遍历检查
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt += 1;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    cnt = test_nums_len - 1;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt -= 1;
    }
    if (cnt == -1) {
        LOG_TEST_PASS("for each rb_node test(inv) succeed!\n");
    }

    /// 进行第二次左旋操作
    for (cnt = 0; cnt < rotate_left_nums_len; cnt++) {
        struct rb_node *tmp_node = rb_find_key(root, (unsigned long)(rotate_left_nums + cnt));
        if (tmp_node == NULL) {
            LOG_TEST_FAIL("failed to find node! ");
            printf("cnt: %d, key: %d\n", cnt, rotate_left_nums[cnt]);
            break;
        }
        current = *(int*)(rb_get_node_key(root, tmp_node));
        if (rotate_left_nums[cnt] != current) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, key: %d, current: %d\n", 
                cnt, rotate_left_nums[cnt], current);
            break;
        }
        __rb_rotate_left(root, tmp_node);
    }

    if (cnt == rotate_left_nums_len) {
        LOG_TEST_PASS("rotation complete!\n");
    }

    /// 顺序遍历检查
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt += 1;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    cnt = test_nums_len - 1;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt -= 1;
    }
    if (cnt == -1) {
        LOG_TEST_PASS("for each rb_node test(inv) succeed!\n");
    }

    /// 进行第二次右旋操作
    for (cnt = 0; cnt < rotate_right_nums_len; cnt++) {
        struct rb_node *tmp_node = rb_find_key(root, (unsigned long)(rotate_right_nums + cnt));
        if (tmp_node == NULL) {
            LOG_TEST_FAIL("failed to find node! ");
            printf("cnt: %d, key: %d\n", cnt, rotate_right_nums[cnt]);
            break;
        }
        current = *(int*)(rb_get_node_key(root, tmp_node));
        if (rotate_right_nums[cnt] != current) {
            LOG_TEST_FAIL("find the wrong node! ");
            printf("cnt: %d, key: %d, current: %d\n", 
                cnt, rotate_right_nums[cnt], current);
            break;
        }
        __rb_rotate_right(root, tmp_node);
    }

    if (cnt == rotate_right_nums_len) {
        LOG_TEST_PASS("rotation complete!\n");
    }

    /// 顺序遍历检查
    cnt = 0;
    rb_foreach_entry_safe(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt += 1;
    }
    if (cnt == test_nums_len) {
        LOG_TEST_PASS("for each rb_node test succeed!\n");
    }

    cnt = test_nums_len - 1;
    rb_foreach_entry_safe_inv(root, pos, n, rb_entry) {
        current = pos->key;
        if (current != test_nums_sorted[cnt]) {
            LOG_TEST_FAIL("current: %d, cnt: %d, num: %d\n", current, cnt, test_nums_sorted[cnt]);
            break;
        }
        cnt -= 1;
    }
    if (cnt == -1) {
        LOG_TEST_PASS("for each rb_node test(inv) succeed!\n");
    }

    /// 清理测试现场
    free(test_nums_sorted);
    DESTROY_RB_TREE(root);
}

void bintree_simple_test(void)
{
    printf("\n* bintree_simple_test:\n");
    bintree_basic_test();
    bintree_simple_rotate_test();
}
